In recent years, ATM communication has become increasingly popular. Prior to this preference for ATM, time division multiplexing (TDM) systems were the preferred mode of communication. In TDM systems, each user was allocated a particular time slot within a standard time interval during which a communication channel would be dedicated to the user. In this system, the time slot would be unavailable to other users regardless of whether the allocated user was actually using it which frequently resulted in wasted bandwidth.
In ATM systems, by contrast, information is transmitted as bandwidth is available without regard to time. In order to keep ATM traffic flowing, each user agrees, by way of a contract with the ATM network operator, to a minimum length of time, t, between transmission of his or her cells. A maximum number of cells which may be transmitted in an interval, T, is also agreed upon. The time, t, determines the user's peak cell rate (PCR) and the interval, T, determines the user's sustained cell rate (SCR). A third parameter, maximum burst size (MBS) which specifies the maximum number of cells which are permitted to be transmitted consecutively at the PCR, is also contracted for. In order to prevent users from exceeding their respective limitations, ATM networks may employ a UPC device which can monitor these and other usage parameters.
In an ATM system, UPC monitoring is typically performed in accordance with standard generic cell rate algorithms (GCRAs). Once such GCRA is a “leaky bucket” algorithm, in which a figurative bucket “fills” proportional to the actual cell rate received from a user and “drains” at a fixed rate proportional to the contracted service rate parameters. If the user exceeds the limits on contracted parameters, such as PCR or SCR, the “bucket” will “overflow” and the user's cells may be either discarded or tagged as having a low priority.
ATM communications may be carried out using a constant bit rate (CBR) or using a variable bit rate (VBR). A CBR connection essentially mimics the old TDM systems. Monitoring of a CBR connection is accomplished using a single leaky bucket. Conformance is characterized by the peak cell rate (PCR) and the corresponding cell delay variation tolerance (CDVT) due to, e.g., head-of-line blocking. The CDVT is defined in relation to the PCR. The capacity of the leaky bucket is 1/PCR (a.k.a. IP)+CDVT specified for the cell flow. The drain rate of the PCR bucket is 1/PCR.
FIG. 1 is a flow chart illustrating the operation of a leaky bucket GCRA used to monitor usage parameters for a CBR connection. In block 102, a cell arrives at timeT. Thereafter TTATp for the particular user is read from memory in block 105. TTATp is the time value at which the “bucket” will have drained to an empty condition in the absence of new cell arrivals. It is calculated during cell arrivals and is adjusted in proportion to the contracted PCR rate for CBR service. In Block 107 a comparison between TTA and TTATp is performed. If TTA is greater than TTATp, i.e. the cell arrived after the bucket had completely emptied, then the cell is accepted at block 111, and, at block 114, TTATp is set to TTA+1/PCR. If TTA is not greater than TTATp, i.e. the bucket is not completely empty, a check is done in block 117 to determine if there is enough room in the partially full bucket to accept the cell based on its maximum capacity of 1/PCR+CDVT. If not, the cell is discarded at block 120. If so, the cell is accepted at block 122, and TTATp is updated at block 125 to equal TTATp+1/PCR.
In a variable bit rate (VBR) system, a second leaky bucket GCRA is used in addition to the first leaky bucket GCRA described above in order to ensure compliance with the contracted sustained cell rate (SCR) and maximum burst size (MBS). The capacity of this second leaky bucket is 1/SCR+Burst Tolerance (BT)+CDVT. Burst tolerance is calculated from the contracted SCR, PCR, and MBS, and is the additional bucket depth required to hold “MBS−1” more cells arriving at the PCR rate (BT={MBS−1}×{1/SCR−1/PCR}). The sum of BT and CDVT is given the identifier “L”. The drain rate of this bucket is 1/SCR
FIG. 2 shows the flow diagram for this second GCRA for the case where it is used in conjunction with the GCRA of FIG. 1. If a cell is accepted in accordance with the GCRA of FIG. 1, i.e., either of boxes 128 or 131 of FIG. 1 are reached, then TTATs is retrieved from memory in block 137. TTATs is the time value at which the “bucket” will have drained to an empty condition in the absence of new cell arrivals, and is calculated in increments of 1/SCR which provides enough time for a full bucket to leak enough to provide room for another cell. A comparison between the TTA of the cell from box 102 of FIG. 1 and the theoretical arrival time, TTATs, is then performed at box 140.
If the result of the comparison of box 140 is that TTA is greater than TTATs, then the cell is accepted at box 143, and TTATs is set to TTA+1/SCR at box 146. If the result of box 140 is that TTA is not greater than TTATs, then the system checks at box 149 to see whether the sum of TTA plus the burst tolerance (BT) plus the CDVT is greater than TTATs, where BT is a function of the contracted parameters MBS, PCR and SCR. If not, the cell is non-conforming and is discarded at box 152. If, on the other hand, the condition TTA+BT+CDVT>TTATs is met, the cell is accepted at box 155 and TTATs is set to TTATs+1/SCR at box 158.
A brief example using simple, if not practical, hypothetical figures for SCR, MBS and PCR will better illustrate the operation of the leaky bucket of FIG. 2. Assuming a VBR service with contracted parameters of SCR=5 cells/sec, a MBS=3 cells, and a PCR of 100 cells/sec and CDVT of 0.02 sec. This results in 1/SCR=IS=0.2 sec/cell, BT=0.38 sec, and L=BT+CDVT=0.4 sec. For the purposes of this example, assume that the criteria of the first leaky bucket check against PCR and CDVT is always favorable and that the initial value of TTATs is 0.0. If a first cell is transmitted at 0.01 seconds, i.e., TTA=0.01, the result of box 140 is that TTA>TTATs so that the cell is accepted at box 143 and TTATs is set to TTATs+1/SCR, i.e., 0.0+0.2=0.2 sec at box 146. A second cell now arrives at time 0.02 seconds. The result of box 140 is that TTA<TTATs so that the condition TTA+L>TTATs is checked at box 149. We find that this condition is met (0.02+0.4>0.2). The cell is accepted at box 155 and TTATs is set to TTATs+1/SCR, i.e., 0.2+0.2=0.4 sec at box 158. Similarly, a third cell arrivals at 0.03 sec, the cell is accepted and TTATs is set to 0.6 sec. If a fourth cell arrives at 0.04 sec, TTA+L will not be greater than TTATs. The fourth cell is therefore discarded at box 152 and TTATS remains unchanged at 0.6 sec. The same result occurs for any cell received earlier than time 0.2 seconds. After that time, the condition TTA+L>TTATs of box 149 is again met. Furthermore, if the fifth cell does not arrive until a time later than 0.6 sec, the bucket will be completely empty and the TTA>TTATs condition will be met.
Those skilled in the art will appreciate that the above description is a simplified explanation of ATM systems, the role of UPC devices and leaky buckets generally. With respect to ATM systems, detailed explanations of the operation of such systems may be found in User Network Interface Specification (UNI) 3.1 published by the ATM Forum. The present invention is intended for use in systems designed in accordance with the standards presented therein, but is not so limited. Moreover, leaky bucket GCRAs have myriad design applications in which the present invention may be employed.
While the UNI Specification provides broad standards for designing ATM systems, there is little or no guidance provided for many practical problems encountered in implementation. One such problem is that counters and registers of infinite memory are not available to keep track of time, and finite-memory counters and registers will eventually reach their limit and reset to zero. This problem is hereafter referred to as “wrapping.” A wrapping of the current time counter from which the cell arrival time TTA is read and/or the register which stores TTA without a consequent wrapping of the register which stores the theoretical arrival time TTAT will cause subsequent comparisons between TTAT and TTA to yield unwanted results. For example, if the current time counter wraps to zero, it will appear that the arrival time, TTA, is much earlier than it actually is, and the comparison between TTA and TTAT will show that TTA is less than TTAT, indicating a violation of the contracted transmission rate when, in fact, no such violation occurred.